package com.mk.web.structure.search;

import java.util.Arrays;

/**
 * 二分查找
 * Created by WangChen on 2018/12/18 17:57.
 */
public class BinarySearch {

    public static void main(String [] args){
        int[] array = {6, 5, 7, 3, 8, 2};// 1.查找范围
        int key = 8;// 2.查找目标
        Arrays.sort(array);// 3.如果无序, 则要先排序
        // 具体查找方法
//        int index = binarySearch(array, key);
        int index = binarySearchByRecursive(array, key);
        // 结果输出
        System.out.println(index == -1 ? "不存在" : index);
    }

    /**
     * 不使用递归
     * T(n) =O(logn)
     * S(n) =O(1)
     */
    private static int binarySearch(int[] arr, int key){
//        int index = -1;
        int low = 0; int high = arr.length -1;
        while (low <= high){
            int mid = (low + high) >> 1;// 相当于除于2, 并向下取整
            if (key == arr[mid]){
                return mid;
//                break;
            }else if (key < arr[mid]){
                high = mid - 1;
            }else {
                low = mid + 1;
            }
        }
        return -1;
    }

    private static int binarySearchByRecursive(int[] arr, int key){
        return binarySearch(arr, key, 0, arr.length -1);
    }

    /**
     * 使用递归
     * T(n) = O(logn)
     * S(n) = O(logn)
     */
    private static int binarySearch(int[] arr, int key, int low, int high){
        if (low > high){
            return -1;
        }
        int mid = (low + high) >> 1;
        if (key == arr[mid]){
            return mid;
        }else if (key < arr[mid]){
            return binarySearch(arr, key, low, mid -1);
        }else {
            return binarySearch(arr, key, mid + 1, high);
        }
    }
}
